package exampleQuestions;

/**
 * Given a binary tree, write a code that returns the difference between sum of
 * nodes at even level and sum of nodes at odd level. Root is considered at
 * level 0. (written test question. coding.)
 * 
 */
public class SumOfElementsOnEvenLevel {

	static class Node {

		public Node(int i) {
			this.val = i;
		}

		Node left, right;
		int val;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		Node n = new Node(7);
		Node n2 = new Node(4);
		Node n3 = new Node(3);
		Node n4 = new Node(10);
		Node n5 = new Node(4);
		Node n6 = new Node(2);

		n.left = n2;
		n.right = n3;
		n2.left = n6;
		n6.right = n5;
		n3.left = n4;

		System.out.println(diff(n2));
	}

	private static int diff(Node n) {

		return calculateDiff(n, 0, 0);
	}

	private static int calculateDiff(Node n, int level, int sum) {
		if (n != null) {
			int sign = (level % 2 == 0) ? 1 : -1;
			sum += n.val * sign;

			sum += calculateDiff(n.left, level + 1, 0);
			sum += calculateDiff(n.right, level + 1, 0);

		}

		return sum;
	}
}
